package day20210625;

import treenode.SimpleTreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 解决方案
 * 145.二叉树的后序遍历
 * 左——>右——>根
 *
 * @author lizy
 * @date 2021/06/25
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        SimpleTreeNode simpleTreeNode = new SimpleTreeNode();
        simpleTreeNode.val = 1;
        simpleTreeNode.right = new SimpleTreeNode(2);
        simpleTreeNode.right.left = new SimpleTreeNode(3);
        // 后序遍历
        System.out.println(solution.postorderTraversal(simpleTreeNode));
    }

    public List<Integer> postorderTraversal(SimpleTreeNode root){
        List<Integer> res = new ArrayList<>();
        postorder(root,res);
        return res;
    }

    private void postorder(SimpleTreeNode root, List<Integer> res) {
        if (root == null){
            return;
        }
        // 左
        postorder(root.left,res);
        // 右
        postorder(root.right,res);
        // 根
        res.add(root.val);
    }
}
